//<p>给你一个单链表的头节点 <code>head</code> ，请你判断该链表是否为回文链表。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p> 
//<img alt="" src="https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg" style="width: 422px; height: 62px;" /> 
//<pre>
//<strong>输入：</strong>head = [1,2,2,1]
//<strong>输出：</strong>true
//</pre>
//
//<p><strong>示例 2：</strong></p> 
//<img alt="" src="https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg" style="width: 182px; height: 62px;" /> 
//<pre>
//<strong>输入：</strong>head = [1,2]
//<strong>输出：</strong>false
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li>链表中节点数目在范围<code>[1, 10<sup>5</sup>]</code> 内</li> 
// <li><code>0 &lt;= Node.val &lt;= 9</code></li> 
//</ul>
//
//<p>&nbsp;</p>
//
//<p><strong>进阶：</strong>你能否用&nbsp;<code>O(n)</code> 时间复杂度和 <code>O(1)</code> 空间复杂度解决此题？</p>
//
//<div><div>Related Topics</div><div><li>栈</li><li>递归</li><li>链表</li><li>双指针</li></div></div><br><div><li>👍 1477</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import com.rising.leetcode.editor.cn.doc.object.ListNode;

/**
 * 回文链表
 * @author DY Rising
 * @date 2022-08-16 20:44:44
 */
public class P234_PalindromeLinkedList{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P234_PalindromeLinkedList().new Solution();
        //ListNode node = ListNode.buildListNode(new int[]{1,2,3,2,1});
        ListNode node = ListNode.buildListNode(new int[]{1,2,2,1});
        System.out.println(solution.isPalindrome(node));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        //快慢指针，慢指针一次走一步，快指针一次走两步
        ListNode pre = null;
        ListNode cur = null;
        while (fast != null && fast.next != null) {
            //再遍历的过程中将链表翻转
            //记录下当前位置
            cur = slow;
            //完成快慢指针
            slow = slow.next;
            fast = fast.next.next;
            cur.next = pre;
            pre = cur;
        }
        //有可能存在奇数，慢指针再走一步
        if (fast != null) {
            slow = slow.next;
        }
        //快指针走到尾部后，直接用慢指针的链表和cur链表进行对比
        while (cur !=null && slow != null) {
            if (cur.val != slow.val) {
                return false;
            }
            cur = cur.next;
            slow = slow.next;
        }
        /*if (cur != null || slow != null) {
            //说明不是偶数个
            return false;
        }*/
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
